package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class _155_MinStack {
    public static void main(String[] args) {
        MinStack minStack = new _155_MinStack().new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int min = minStack.getMin();
        minStack.pop();
        int top = minStack.top();
        int min1 = minStack.getMin();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 栈 + 堆
    /*class MinStack1 {
        PriorityQueue<Integer> heap;
        Deque<Integer> stack;

        */

    /**
     * initialize your data structure here.
     *//*
        public MinStack() {
            heap = new PriorityQueue<>();
            stack = new LinkedList<>();
        }

        public void push(int val) {
            heap.add(val);
            stack.push(val);
        }

        public void pop() {
            heap.remove(stack.peek());
            stack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return heap.peek();
        }
    }*/

    // 两个栈
    class MinStack {
        Deque<Integer> stack;
        Deque<Integer> minStack;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            stack = new LinkedList<>();
            minStack = new LinkedList<>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int val) {
            stack.push(val);
            minStack.push(Math.min(val, minStack.peek()));
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)

}